\documentclass[a4paper,12pt]{article}

\usepackage[utf8]{inputenc}
\usepackage[T2A]{fontenc}
\usepackage[russian]{babel}

\usepackage{amsmath}

\renewcommand{\epsilon}{\varepsilon}
\newcommand{\PR}{\mathop{\mathrm{PR}}\nolimits}

\begin{document}

\section*{Вопрос \No2.16}
{\em Архитектура поисковых систем. PageRank. Автоматическая
классификация текстов. Семантические сети, Semantic web.
Оценка качества результатов поиска.}


\section{Архитектура поисковых систем}

\begin{itemize}
\item Поисковый робот (web crawler). Ходит по ссылкам в Интернете
и индексирует найденные документы, занося в базу данных.
\item База данных. Накапливает информацию о найденных страницах
в формате, удобном для использования алгоритмами поиска: прямой
(документ "--- слова) и обратный (слово "--- документы) индексы.
\item Клиент. Обрабатывает поисковые запросы пользователей, извлекая
информацию из базы данных.
\end{itemize}

Альтернативные архитектуры.
\begin{itemize}
\item Распределенная поисковая система: база данных распределена
по ряду серверов.
\item Метапоисковая система: вместо собственного поискового робота
и базы данных используются запросы к другим поисковым системам.
\end{itemize}


\section{PageRank}

PageRank "--- алгоритм ранжирования результатов поиска. Ранжирование
производится по рейтингу, вычисляемому через количество ссылок
на данный документ и рейтинги ссылающихся документов.

PageRank использует модель случайного блуждания.
\begin{itemize}
\item Ориентированный граф: документы "--- вершины, ссылки "--- дуги.
\item Начинаем в случайной вершине.
\item С вероятностью $\epsilon$ переходим в случайную вершину.
\item С вероятностью $1-\epsilon$ переходим по случайной исходящей дуге.
\end{itemize}

$\PR_k(i)$ "--- вероятность находиться в вершине $i$ на $k$-м шаге.
$\PR_0(i)=1/n$, где $n$ "--- количество вершин.

$\PR(i)=\lim_{k\to\infty}\PR_k(i)$.
На практике ограничиваются $\PR_{50}(i)$.

Важные соотношения:
\begin{align*}
\PR_k(i)&=\epsilon+(1-\epsilon)\sum_{j:\;j\to i}\frac{\PR_{k-1}(j)}{|\{l:j\to l\}|},\\
\lim_{k\to\infty}:\quad \PR(i)&=\epsilon+(1-\epsilon)\sum_{j:\;j\to i}\frac{\PR(j)}{|\{l:j\to l\}|},
\end{align*}
где $x\to y$ означает наличие дуги из~$x$ в~$y$.

PageRank в векторной форме.
\begin{itemize}
\item $\overline{\PR}_k=(\PR_k(1),\dots,\PR_k(n))^{T}$
\item $L=(l_{ij})$:
\begin{itemize}
\item $l_{ij}=\epsilon+(1-\epsilon)\frac{1}{|\{l:j\to l\}|}$, если $j\to i$,
\item $l_{ij}=\epsilon$ иначе.
\end{itemize}
\item $\overline{\PR}_k=L^k\overline{\PR}_0$
\item $\overline{\PR}=L\overline{\PR}$, т.е. $\overline{\PR}$ "---
собственный вектор матрицы~$L$.
\end{itemize}


\section{Автоматическая классификация текстов.}

Постановка задачи.
\begin{itemize}
\item Множество документов $D=\{D_1,\dots,D_n\}$.
\item Множество категорий $C=\{C_1,\dots,C_m\}$.
\item Неизвестная функция $\Phi:D\times C\to\{0,1\}$.
\item Задача: построить классификатор $\Phi'$, максимально близкий к $\Phi$.
\item Иногда достаточно построить $\Phi'':D\times C\to[0,1]$, который задает
не точную классификацию, а ранжирование категорий для каждого документа.
\item От ранжирования легко перейти к точной классификации, введя
некоторый порог $0<t<1$: $\Phi'(D_i,C_j)=1\iff \Phi''(D_i,C_j)\ge t$.
\end{itemize}

Применение.
\begin{itemize}
\item Фильтрация документов, распознавание спама.
\item Наполнение интернет-каталогов.
\item Классификация новостей.
\item Контекстная реклама.
\item Персональные новости.
\end{itemize}

Пусть каждый документ $D_i$ представлен в виде вектора весов термов
$(t_1,\dots,t_p)$. Рассмотрим пример линейного on-line классификатора.
\begin{itemize}
\item $\Phi'(D_i,C_j)=\frac{D_i\cdot C_j}{|D_i| |C_j|}$, где векторы
коэффициентов $C_j$ вычисляются динамически по мере обработки
обучающего множества.
\item Начинаем с $C_j=(1,\dots,1)$.
\item Для каждого учебного документа применяем текущее правило.
\item При неудаче вносим поправки $+\alpha$/$-\beta$ в коэффициенты,
соответствующие термам неправильно классифицированного документа.
\end{itemize}


\section{Семантические сети, Semantic web.}

Семантическая сеть (semantic network) "--- информационная модель
предметной области, имеющая вид ориентированного графа,
вершины которого соответствуют объектам предметной области,
а дуги задают отношения между ними.

Семантические сети бывают однородными (только один тип отношения)
и неоднородными (разные типы отношений).

Semantic Web "--- часть глобальной концепции развития сети Интернет,
целью которой является реализация возможности машинной обработки
информации за счет использования семантических сетей для описания
документов и их отношений.

Преимущества Semantic Web.
\begin{itemize}
\item Семантический поиск.
\item Вопросо-ответные системы.
\item Агенты в семантическом Вебе.
\item Объединение знаний (интеграция баз данных).
\end{itemize}

Языки описания для Semantic Web (основаны на XML).
\begin{itemize}
\item RDF (Resource Description Framework) "--- описывает
конкретные объекты и их отношения (синтаксис).
\item OWL (Ontology Web Language) "--- описывает
типы объектов и типы отношений (семантика).
\end{itemize}


\section{Оценка качества результатов поиска.}

\begin{itemize}
\item Точность (precision) "--- отношение числа найденных релевантных
документов к общему числу найденных документов.
\item Полнота (recall) "--- отношение числа найденных релевантных
документов к общему числу релевантных документов в базе.
\item F-мера (F-measure, мера Ван Ризбергена) "--- среднее
гармоническое точности и полноты: $F=2PR/(P+R)$.
\end{itemize}


\bigskip
Основной источник информации - курс <<Алгоритмы для Интернета>>:
\texttt{http://yury.name/internet.html}

\end{document}

